Data organization is important in relational database systems that deal with complex queries against large volumes of data. Relational database systems allow data to be stored in tables that are organized as both a set of columns and a set of rows. Standard commands are used to define the columns and rows of tables and data is subsequently entered in accordance with the defined structure. The defined table structure is logically maintained, but may not correspond to the physical organization of the data. For example, the data corresponding to a particular table may be split up among a number of physical hardware storage facilities.
Users of relational database systems require the minimum time possible for execution of complex queries against large amounts of data. Different physical types of storage, for example random access memory and hard drives, incur different length delays. In addition, writing to memory or a hard drive is often slower than reading an equivalent amount of data from memory or a hard drive. The organization of data corresponding to tables defined in a relational database system may determine the number of writes and reads that need to be performed in order to execute a common query. In some situations, particular portions of the data in a table are searched more often than other portions. If the data is properly organized, performance can be improved by searching a part of the data for queries that can take advantage of that organization. If the data is not organized in any way, it will often need to be searched in its entirety to satisfy a query or copied and restructured into a useful organization.
In some cases, it is possible to eliminate large portions of a database prior to executing a query. For instance, an insurance database may cover many years or months. Perhaps the query is directed toward a certain number of months in a year. A table may be created that is partitioned by month for each year. Thus, all the rows in the table may be partitioned by month, and a partitioned primary index points to a first row for each month. It is then possible to quickly identify a starting partition, and eliminate partitions for prior months and future months from consideration. Then, the query may be run over the remaining partitions in the table. This is referred to as a single-level partitioned table with static elimination of partitions that are not needed for a query.
Difficulty arises when a further partitioning of the database may be helpful, such as, in addition to partitioning the database by year and month, a query may only be interested in results from one geographic region, such as a state or states for selected months. This type of partitioning is referred to as multilevel partitioning. While some static partition elimination may occur on a month basis, there is a need to further improve query performance over such multilevel partitioned data, in particular, when the partitions to eliminate cannot be determined statically but require retrieval of information from other tables.